# https://techlog.cn/article/list/10183325
# 经典动态规划问题 -- 青蛙上台阶与 python 的递归优化

# 一只青蛙上台阶，一次只能上一个或两个台阶，如果总共有3个台阶，那么有三种上法：
# 111 -- 每次上一个台阶
# 21 -- 先上两个台阶，再上一个台阶
# 12 -- 先上一个台阶，再上两个台阶
# 那么对于 n 个台阶，有多少种上法呢？

import time
import sys


def jump_floor(number) -> int:
    """简单递归"""
    if number == 0:
        return 0
    if number == 1:
        return 1
    if number == 2:
        return 2
    return jump_floor(number - 1) + jump_floor(number - 2)


if __name__ == "__main__1":
    startTime = time.time()
    print(jump_floor(40))
    # 165580141
    # time consuming: 49.11511421203613
    print(f"time consuming: {time.time() - startTime}")

# 上述递归过程之所以耗时，是因为每一次递归都需要在栈中开辟新的调用栈执行子方法，在栈
# 的反复开辟、销毁过程中，不仅耗时激增，最为关键的是，反复的栈开辟让内存占用率急剧增长

# 在 C 语言中，编译器有一个概念 -- 尾递归，当编译器检测到一个函数调用的递归是函数的
# 最后一行，那么编译器就覆盖当前的栈而不是在当前栈中去创建一个新的栈

# 下面我们将上述代码改为尾递归的方式，基本思路是通过一个参数来保存上次执行结果，另一
# 个参数保存累计值


def jump_floor_1(number) -> int:
    """尾递归"""
    if number == 0:
        return 0
    if number == 1:
        return 1
    if number == 2:
        return 2
    return solute(number, 0, 1)


def solute(number, pre, sum) -> int:
    if number == 0:
        return sum
    return solute(number - 1, sum, pre + sum)


if __name__ == "__main__2":
    startTime = time.time()
    print(jump_floor_1(40))
    # 165580141
    # time consuming: 0.000997304916381836
    print(f"time consuming: {time.time() - startTime}")

# 上述代码如果将台阶层数增加到几千就会抛出异常：
# RecursionError: maximum recursion depth exceeded in comparison

# 可以看到，python 解释器并不会像 C 语言编译器一样对尾递归进行优化

# 上述代码之所以能够让时间复杂度、空间复杂度大幅下降，其唯一的原因是将原有的两次创建
# 栈、压栈、销毁的一系列工作变为了一次，而问题并没有从根本上解决

# 怎么才能像 C 语言一样，在每次递归调用完成后，自动清理原有的栈呢？

# 在捕获异常后，作为异常处理的一个环节，python 解释器会自动清理原有的栈，那么通过
# python 的异常机制，我们就可以实现上述功能


def jump_floor_2(number) -> int:
    """尾递归"""
    if number == 0:
        return 0
    if number == 1:
        return 1
    if number == 2:
        return 2
    return solute2(number, 0, 1)


class TailRecurseException(Exception):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs


def tail_call_optimized(g):
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs

    return func


@tail_call_optimized
def solute2(number, pre, sum) -> int:
    if number == 0:
        return sum
    return solute2(number - 1, sum, pre + sum)


if __name__ == "__main__3":
    startTime = time.time()
    print(jump_floor_2(4000))
    # time consuming: 0.013962507247924805
    print(f"time consuming: {time.time() - startTime}")

# 我们通过装饰器的一层封装，每一次祖父调用与当前调用相同时就标志着递归的发生，因为父
# 调用是装饰器中的调用，祖父调用与当前调用都是原代码中的函数调用，相同就说明了递归的
# 发生

# 通过抛出异常清理栈空间，同时异常类中记录了当前参数，捕获异常后继续使用当前参数调
# 用，这就解决了栈深度不断增加的问题

# 需要注意的是，原代码必须是尾递归的方式才可以用该装饰器优化，否则将导致后续代码无法
# 执行，从而得到错误的结果

# 上述的所有问题其实都是递归引起的，而任何一个递归的方法都可以转换为迭代法，尤其是我
# 们本文的这个问题：

# f(n)＝f(n-1)＋f(n-2)

# 这就是斐波那契数列


def jump_floor_3(number) -> int:
    """迭代法——斐波那契数列"""
    one = 1
    two = 2
    if number == 0:
        return 0
    if number == 1:
        return one
    if number == 2:
        return two
    count = 0
    for cur in range(3, number + 1):
        count = one + two
        if cur % 2:
            one = count
        else:
            # 能整除，为False
            two = count
    return count


if __name__ == '__main__':
    starttime = time.time()
    print(jump_floor_3(4000))
    # 耗时：0.0040051937103271484
    print('耗时：' + str(time.time() - starttime))
